package Sep.Next;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Five {
    public static void main(String[] args) {
        Solution s = new Solution();
        Node n1 = new Node (1);
        Node n2 = new Node (2);
        Node n3 = new Node (3);
        Node n4 = new Node (4);
        Node n5 = new Node (5);
        Node n7 = new Node (7);
        n1.left= n2;
        n1.right = n3;
        n2.left = n4;
        n2.right = n5;
        n3.left = null;
        n3.right = n7;
        n4.left = null;
        n4.right = null;
        n5.left = null;
        n5.right = null;
        n7.left = null;
        n7.right = null;
        s.connect(n1);
    }
    
}
// 117. 填充每个节点的下一个右侧节点指针 II


class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
}

class Solution {
    public Node connect(Node root) {
        if(root==null) return null;
        Queue<Node> que = new LinkedList<>();
        que.add(root);
        Node pre = null;
        while(!que.isEmpty()){
            int len = que.size();
            for(int i=0;i<len;i++){
                Node n = que.poll();
                if(n.left!=null) que.offer(n.left);
                if(n.right!=null) que.offer(n.right);
                if(pre!=null) pre.next = n;
                if(i==len-1){
                    n.next = null;
                    pre = null;
                }else{
                    pre= n;
                }
            }
        }
        return root;
    }
}
